import random
import numpy as np
import copy
import time
import pickle
import os
import matplotlib.pyplot as plt
from typing import List, Dict, Tuple, Optional, Union
from matplotlib.patches import Rectangle

# ========================= 全局配置 =========================
INSTANCE_NUM = 24  # 算例总数
INSTANCE_JOBS = list(range(3, 3 + INSTANCE_NUM))  # 每个算例的作业数：3~26（递增1）
INSTANCE_FOLDER = "instances"  # 算例保存文件夹
PLOT_FOLDER = "plots"  # 图表保存文件夹
# 生产参数配置（所有算例共用，保证一致性）
DEFAULT_PARAMS = {
    "m_gas": 2,  # 配气设备数量
    "m_mix": 1,  # 混匀设备数量
    "m_test": {"A": 2, "B": 2, "C": 2, "D": 2},  # 各组分检测设备数（≥2）
    "k_gas": 2.0,  # 配气时间基数（配气时间=组分数量×k_gas）
    "k_mix": 3.0  # 混匀时间基数（混匀时间=组分数量×k_mix）
}
# 算法参数配置
ALGORITHM_PARAMS = {
    "GA": {"pop_size": 50, "max_iter": 200, "crossover_rate": 0.8, "mutation_rate": 0.1, "tournament_size": 5},
    "SA": {"init_temp": 100.0, "cool_rate": 0.95, "max_iter": 1000, "inner_iter": 50},
    "PSO": {"pop_size": 50, "max_iter": 200, "w": 0.7, "c1": 1.5, "c2": 1.5},
    "TS": {"tabu_size": 20, "max_iter": 1000, "neighbor_num": 50}
}


# ========================= 数据结构定义 =========================
class Job:
    """标气作业类：存储单个气瓶的生产参数"""

    def __init__(self, job_id: int, components: List[str], t_test: Dict[str, float]):
        self.job_id = job_id  # 作业ID
        self.components = components  # 组分列表（如["A", "B", "C"]）
        self.t_test = t_test  # 各组分检测时间（如{"A": 8, "B": 10}）
        self.t_gas = 0.0  # 配气时间（组分数量×k_gas）
        self.t_mix = 0.0  # 混匀时间（组分数量×k_mix）

    def to_dict(self) -> Dict:
        """转换为字典（用于序列化）"""
        return {
            "job_id": self.job_id,
            "components": self.components,
            "t_test": self.t_test,
            "t_gas": self.t_gas,
            "t_mix": self.t_mix
        }

    @staticmethod
    def from_dict(data: Dict) -> "Job":
        """从字典重构对象（用于反序列化）"""
        job = Job(
            job_id=data["job_id"],
            components=data["components"],
            t_test=data["t_test"]
        )
        job.t_gas = data["t_gas"]
        job.t_mix = data["t_mix"]
        return job


class Params:
    """生产参数类：存储设备数量和时间基数"""

    def __init__(
            self,
            m_gas: int = 2,
            m_mix: int = 1,
            m_test: Dict[str, int] = None,
            k_gas: float = 2.0,
            k_mix: float = 3.0
    ):
        self.m_gas = m_gas
        self.m_mix = m_mix
        self.m_test = m_test if m_test else {}
        self.k_gas = k_gas
        self.k_mix = k_mix

    def validate(self):
        """验证参数合法性"""
        for c, num in self.m_test.items():
            if num < 2:
                raise ValueError(f"组分{c}的检测设备数量必须≥2，当前为{num}")

    def to_dict(self) -> Dict:
        """转换为字典（用于序列化）"""
        return {
            "m_gas": self.m_gas,
            "m_mix": self.m_mix,
            "m_test": self.m_test,
            "k_gas": self.k_gas,
            "k_mix": self.k_mix
        }

    @staticmethod
    def from_dict(data: Dict) -> "Params":
        """从字典重构对象（用于反序列化）"""
        return Params(
            m_gas=data["m_gas"],
            m_mix=data["m_mix"],
            m_test=data["m_test"],
            k_gas=data["k_gas"],
            k_mix=data["k_mix"]
        )


class ScheduleInfo:
    """调度信息类：记录作业在各阶段的详细调度结果（用于绘制甘特图）"""

    def __init__(self):
        # 配气阶段：{job_idx: (start_time, end_time, machine_id)}
        self.gas_schedule: Dict[int, Tuple[float, float, int]] = {}
        # 混匀阶段：{job_idx: (start_time, end_time, machine_id)}
        self.mix_schedule: Dict[int, Tuple[float, float, int]] = {}
        # 分析阶段：{job_idx: (start_time, end_time, component_machines)}，component_machines: {组分: 设备ID}
        self.test_schedule: Dict[int, Tuple[float, float, Dict[str, int]]] = {}
        self.makespan = 0.0  # 最大完工时间


# ========================= 核心工具函数 =========================
def calculate_makespan_with_schedule(jobs: List[Job], params: Params, job_order: List[int]) -> ScheduleInfo:
    """
    计算Makespan并返回详细调度信息（用于甘特图）
    :return: ScheduleInfo对象
    """
    schedule = ScheduleInfo()

    # -------------------------- 1. 配气阶段 --------------------------
    gas_machines = [0.0] * params.m_gas
    for job_idx in job_order:
        job = jobs[job_idx]
        min_avail = min(gas_machines)
        machine_id = gas_machines.index(min_avail)
        t_start = max(min_avail, 0.0)
        t_end = t_start + job.t_gas
        schedule.gas_schedule[job_idx] = (t_start, t_end, machine_id)
        gas_machines[machine_id] = t_end

    # -------------------------- 2. 混匀阶段 --------------------------
    mix_machines = [0.0] * params.m_mix
    for job_idx in job_order:
        job = jobs[job_idx]
        min_avail = min(mix_machines)
        machine_id = mix_machines.index(min_avail)
        t_start = max(min_avail, schedule.gas_schedule[job_idx][1])
        t_end = t_start + job.t_mix
        schedule.mix_schedule[job_idx] = (t_start, t_end, machine_id)
        mix_machines[machine_id] = t_end

    # -------------------------- 3. 分析阶段 --------------------------
    test_machines = {c: [0.0] * params.m_test[c] for c in params.m_test}
    for job_idx in job_order:
        job = jobs[job_idx]
        components = job.components
        comp_min_avail = {}
        comp_machine_id = {}
        for c in components:
            avail_times = test_machines[c]
            min_avail = min(avail_times)
            comp_min_avail[c] = min_avail
            comp_machine_id[c] = avail_times.index(min_avail)

        t_start = max(schedule.mix_schedule[job_idx][1], max(comp_min_avail.values()))
        max_test_time = max(job.t_test[c] for c in components)
        t_end = t_start + max_test_time
        schedule.test_schedule[job_idx] = (t_start, t_end, comp_machine_id)

        # 更新检测设备时间
        for c in components:
            machine_id = comp_machine_id[c]
            test_machines[c][machine_id] = t_start + job.t_test[c]

    # 计算最大完工时间
    schedule.makespan = max([t[1] for t in schedule.test_schedule.values()])
    return schedule


def generate_single_instance(n_jobs: int, params: Params) -> List[Job]:
    """生成单个算例的作业列表"""
    components_all = list(params.m_test.keys())  # 所有可选组分
    jobs = []
    for job_id in range(n_jobs):
        # 随机选择2~4个组分
        n_comp = random.randint(2, 4)
        comps = random.sample(components_all, n_comp)
        # 随机生成检测时间（5~15单位时间）
        t_test = {c: random.uniform(5, 15) for c in comps}
        # 创建作业并计算配气/混匀时间
        job = Job(job_id=job_id, components=comps, t_test=t_test)
        job.t_gas = len(comps) * params.k_gas
        job.t_mix = len(comps) * params.k_mix
        jobs.append(job)
    return jobs


def generate_all_instances():
    """生成24个算例并保存到文件夹（存储字典格式，避免自定义类序列化）"""
    # 创建文件夹
    if not os.path.exists(INSTANCE_FOLDER):
        os.makedirs(INSTANCE_FOLDER)

    # 初始化生产参数
    params = Params(
        m_gas=DEFAULT_PARAMS["m_gas"],
        m_mix=DEFAULT_PARAMS["m_mix"],
        m_test=DEFAULT_PARAMS["m_test"],
        k_gas=DEFAULT_PARAMS["k_gas"],
        k_mix=DEFAULT_PARAMS["k_mix"]
    )
    params.validate()

    # 生成每个算例
    for idx in range(INSTANCE_NUM):
        n_jobs = INSTANCE_JOBS[idx]
        jobs = generate_single_instance(n_jobs, params)
        # 将Job和Params转换为字典
        jobs_dict = [job.to_dict() for job in jobs]
        params_dict = params.to_dict()
        # 保存数据
        instance_data = {
            "jobs_dict": jobs_dict,
            "params_dict": params_dict,
            "n_jobs": n_jobs,
            "instance_id": idx + 1
        }
        # 保存路径
        file_path = os.path.join(INSTANCE_FOLDER, f"instance_{idx + 1:02d}.pkl")
        with open(file_path, "wb") as f:
            pickle.dump(instance_data, f)
        print(f"生成算例 {idx + 1:02d}：{n_jobs} 个作业 → 保存至 {file_path}")


def load_instance(instance_id: int) -> Tuple[List[Job], Params, int]:
    """加载指定ID的算例（从字典重构对象）"""
    if instance_id < 1 or instance_id > INSTANCE_NUM:
        raise ValueError(f"算例ID必须在1~{INSTANCE_NUM}之间")

    file_path = os.path.join(INSTANCE_FOLDER, f"instance_{instance_id:02d}.pkl")
    if not os.path.exists(file_path):
        raise FileNotFoundError(f"算例文件不存在：{file_path}")

    with open(file_path, "rb") as f:
        instance_data = pickle.load(f)

    # 从字典重构Job和Params对象
    jobs = [Job.from_dict(data) for data in instance_data["jobs_dict"]]
    params = Params.from_dict(instance_data["params_dict"])
    n_jobs = instance_data["n_jobs"]
    return jobs, params, n_jobs


# ========================= 四种算法实现（带收敛记录） =========================
class GeneticAlgorithm:
    def __init__(self, jobs: List[Job], params: Params, **kwargs):
        self.jobs = jobs
        self.params = params
        self.n_jobs = len(jobs)
        self.pop_size = kwargs.get("pop_size", 50)
        self.max_iter = kwargs.get("max_iter", 200)
        self.crossover_rate = kwargs.get("crossover_rate", 0.8)
        self.mutation_rate = kwargs.get("mutation_rate", 0.1)
        self.tournament_size = kwargs.get("tournament_size", 5)
        self.best_order = None
        self.best_makespan = float('inf')
        self.best_schedule = None
        # 收敛历史：记录每次迭代的最优Makespan
        self.convergence_history = []

    def _initialize_population(self) -> List[List[int]]:
        population = []
        for _ in range(self.pop_size):
            individual = list(range(self.n_jobs))
            random.shuffle(individual)
            population.append(individual)
        return population

    def _fitness(self, individual: List[int]) -> float:
        schedule = calculate_makespan_with_schedule(self.jobs, self.params, individual)
        return schedule.makespan

    def _selection(self, population: List[List[int]], fitnesses: List[float]) -> List[int]:
        candidates = random.sample(list(zip(population, fitnesses)), self.tournament_size)
        candidates.sort(key=lambda x: x[1])  # 最小化Makespan，升序排序
        return candidates[0][0]

    def _ox_crossover(self, parent1: List[int], parent2: List[int]) -> Tuple[List[int], List[int]]:
        start = random.randint(0, self.n_jobs - 2)
        end = random.randint(start + 1, self.n_jobs - 1)
        # 子代1
        child1 = [None] * self.n_jobs
        child1[start:end + 1] = parent1[start:end + 1]
        ptr = 0
        for gene in parent2:
            if gene not in child1:
                while child1[ptr] is not None:
                    ptr += 1
                child1[ptr] = gene
        # 子代2
        child2 = [None] * self.n_jobs
        child2[start:end + 1] = parent2[start:end + 1]
        ptr = 0
        for gene in parent1:
            if gene not in child2:
                while child2[ptr] is not None:
                    ptr += 1
                child2[ptr] = gene
        return child1, child2

    def _mutation(self, individual: List[int]) -> List[int]:
        if random.random() < self.mutation_rate:
            i, j = random.sample(range(self.n_jobs), 2)
            individual[i], individual[j] = individual[j], individual[i]
        return individual

    def run(self) -> Tuple[List[int], float, ScheduleInfo]:
        start_time = time.time()
        population = self._initialize_population()

        for iter in range(self.max_iter):
            # 计算种群适应度（Makespan）
            fitnesses = [self._fitness(ind) for ind in population]
            # 更新当前迭代最优
            current_best_idx = fitnesses.index(min(fitnesses))
            current_best_makespan = fitnesses[current_best_idx]
            current_best_order = population[current_best_idx]
            # 更新全局最优
            if current_best_makespan < self.best_makespan:
                self.best_makespan = current_best_makespan
                self.best_order = copy.deepcopy(current_best_order)
                self.best_schedule = calculate_makespan_with_schedule(self.jobs, self.params, self.best_order)
            # 记录收敛历史
            self.convergence_history.append(self.best_makespan)
            # 生成新一代
            new_population = []
            while len(new_population) < self.pop_size:
                p1 = self._selection(population, fitnesses)
                p2 = self._selection(population, fitnesses)
                # 交叉
                if random.random() < self.crossover_rate:
                    c1, c2 = self._ox_crossover(p1, p2)
                else:
                    c1, c2 = copy.deepcopy(p1), copy.deepcopy(p2)
                # 变异
                c1 = self._mutation(c1)
                c2 = self._mutation(c2)
                new_population.append(c1)
                if len(new_population) < self.pop_size:
                    new_population.append(c2)
            population = new_population

        print(f"GA运行时间：{time.time() - start_time:.2f}s，最优Makespan：{self.best_makespan:.2f}")
        return self.best_order, self.best_makespan, self.best_schedule


class SimulatedAnnealing:
    def __init__(self, jobs: List[Job], params: Params, **kwargs):
        self.jobs = jobs
        self.params = params
        self.n_jobs = len(jobs)
        self.init_temp = kwargs.get("init_temp", 100.0)
        self.cool_rate = kwargs.get("cool_rate", 0.95)
        self.max_iter = kwargs.get("max_iter", 1000)
        self.inner_iter = kwargs.get("inner_iter", 50)
        self.best_order = None
        self.best_makespan = float('inf')
        self.best_schedule = None
        self.convergence_history = []

    def _generate_initial_solution(self) -> List[int]:
        solution = list(range(self.n_jobs))
        random.shuffle(solution)
        return solution

    def _generate_neighbor(self, solution: List[int]) -> List[int]:
        neighbor = copy.deepcopy(solution)
        i, j = random.sample(range(self.n_jobs), 2)
        neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
        return neighbor

    def _calculate_energy(self, solution: List[int]) -> Tuple[float, ScheduleInfo]:
        schedule = calculate_makespan_with_schedule(self.jobs, self.params, solution)
        return schedule.makespan, schedule

    def run(self) -> Tuple[List[int], float, ScheduleInfo]:
        start_time = time.time()
        current_solution = self._generate_initial_solution()
        current_makespan, current_schedule = self._calculate_energy(current_solution)
        self.best_order = copy.deepcopy(current_solution)
        self.best_makespan = current_makespan
        self.best_schedule = current_schedule
        self.convergence_history.append(self.best_makespan)

        temp = self.init_temp
        iter_count = 0

        for _ in range(self.max_iter):
            for _ in range(self.inner_iter):
                neighbor = self._generate_neighbor(current_solution)
                neighbor_makespan, neighbor_schedule = self._calculate_energy(neighbor)
                delta = neighbor_makespan - current_makespan
                # Metropolis准则
                if delta < 0 or random.random() < np.exp(-delta / temp):
                    current_solution = neighbor
                    current_makespan = neighbor_makespan
                    current_schedule = neighbor_schedule
                    # 更新全局最优
                    if current_makespan < self.best_makespan:
                        self.best_makespan = current_makespan
                        self.best_order = copy.deepcopy(current_solution)
                        self.best_schedule = neighbor_schedule
            # 记录收敛历史（每外层迭代记录1次）
            self.convergence_history.append(self.best_makespan)
            temp *= self.cool_rate
            iter_count += 1
            if temp < 1e-6:
                break

        # 确保收敛历史长度与最大迭代次数一致
        while len(self.convergence_history) < self.max_iter:
            self.convergence_history.append(self.best_makespan)

        print(f"SA运行时间：{time.time() - start_time:.2f}s，最优Makespan：{self.best_makespan:.2f}")
        return self.best_order, self.best_makespan, self.best_schedule


class ParticleSwarmOptimization:
    def __init__(self, jobs: List[Job], params: Params, **kwargs):
        self.jobs = jobs
        self.params = params
        self.n_jobs = len(jobs)
        self.pop_size = kwargs.get("pop_size", 50)
        self.max_iter = kwargs.get("max_iter", 200)
        self.w = kwargs.get("w", 0.7)
        self.c1 = kwargs.get("c1", 1.5)
        self.c2 = kwargs.get("c2", 1.5)
        self.positions: List[np.ndarray] = []
        self.velocities: List[np.ndarray] = []
        self.p_best_pos: List[np.ndarray] = []
        self.p_best_makespan: List[float] = []
        self.g_best_pos: np.ndarray = None
        self.g_best_makespan = float('inf')
        self.g_best_order = None
        self.g_best_schedule = None
        self.convergence_history = []

    def _position_to_order(self, position: np.ndarray) -> List[int]:
        return np.argsort(-position).tolist()

    def _fitness(self, position: np.ndarray) -> Tuple[float, ScheduleInfo]:
        job_order = self._position_to_order(position)
        schedule = calculate_makespan_with_schedule(self.jobs, self.params, job_order)
        return schedule.makespan, schedule

    def _initialize_particles(self):
        for _ in range(self.pop_size):
            pos = np.random.uniform(0, 10, self.n_jobs)
            self.positions.append(pos)
            vel = np.random.uniform(-1, 1, self.n_jobs)
            self.velocities.append(vel)
            # 初始化个体最优
            p_makespan, p_schedule = self._fitness(pos)
            self.p_best_pos.append(copy.deepcopy(pos))
            self.p_best_makespan.append(p_makespan)
            # 初始化全局最优
            if p_makespan < self.g_best_makespan:
                self.g_best_makespan = p_makespan
                self.g_best_pos = copy.deepcopy(pos)
                self.g_best_order = self._position_to_order(pos)
                self.g_best_schedule = p_schedule

    def run(self) -> Tuple[List[int], float, ScheduleInfo]:
        start_time = time.time()
        self._initialize_particles()
        self.convergence_history.append(self.g_best_makespan)

        for _ in range(self.max_iter - 1):
            for i in range(self.pop_size):
                # 更新速度
                r1 = np.random.random(self.n_jobs)
                r2 = np.random.random(self.n_jobs)
                vel = (self.w * self.velocities[i] +
                       self.c1 * r1 * (self.p_best_pos[i] - self.positions[i]) +
                       self.c2 * r2 * (self.g_best_pos - self.positions[i]))
                self.velocities[i] = vel
                # 更新位置
                pos = self.positions[i] + vel
                self.positions[i] = pos
                # 计算适应度
                current_makespan, current_schedule = self._fitness(pos)
                # 更新个体最优
                if current_makespan < self.p_best_makespan[i]:
                    self.p_best_makespan[i] = current_makespan
                    self.p_best_pos[i] = copy.deepcopy(pos)
                    # 更新全局最优
                    if current_makespan < self.g_best_makespan:
                        self.g_best_makespan = current_makespan
                        self.g_best_pos = copy.deepcopy(pos)
                        self.g_best_order = self._position_to_order(pos)
                        self.g_best_schedule = current_schedule
            # 记录收敛历史
            self.convergence_history.append(self.g_best_makespan)

        print(f"PSO运行时间：{time.time() - start_time:.2f}s，最优Makespan：{self.g_best_makespan:.2f}")
        return self.g_best_order, self.g_best_makespan, self.g_best_schedule


class TabuSearch:
    def __init__(self, jobs: List[Job], params: Params, **kwargs):
        self.jobs = jobs
        self.params = params
        self.n_jobs = len(jobs)
        self.tabu_size = kwargs.get("tabu_size", 20)
        self.max_iter = kwargs.get("max_iter", 1000)
        self.neighbor_num = kwargs.get("neighbor_num", 50)
        self.tabu_list: List[Tuple[int, int]] = []
        self.best_order = None
        self.best_makespan = float('inf')
        self.best_schedule = None
        self.convergence_history = []

    def _generate_initial_solution(self) -> List[int]:
        solution = list(range(self.n_jobs))
        random.shuffle(solution)
        return solution

    def _generate_neighbors(self, solution: List[int]) -> List[List[int]]:
        neighbors = []
        used_swaps = set()
        while len(neighbors) < self.neighbor_num and len(used_swaps) < self.n_jobs * (self.n_jobs - 1) // 2:
            i, j = random.sample(range(self.n_jobs), 2)
            if i > j:
                i, j = j, i
            if (i, j) not in used_swaps:
                used_swaps.add((i, j))
                neighbor = copy.deepcopy(solution)
                neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
                neighbors.append(neighbor)
        return neighbors

    def _is_tabu(self, swap: Tuple[int, int]) -> bool:
        i, j = swap
        if i > j:
            i, j = j, i
        return (i, j) in self.tabu_list

    def _update_tabu_list(self, swap: Tuple[int, int]):
        i, j = swap
        if i > j:
            i, j = j, i
        self.tabu_list.append((i, j))
        if len(self.tabu_list) > self.tabu_size:
            self.tabu_list.pop(0)

    def _get_swap(self, current: List[int], neighbor: List[int]) -> Tuple[int, int]:
        """找到两个解之间的交换对"""
        swap = None
        for i in range(self.n_jobs):
            if current[i] != neighbor[i]:
                j = neighbor.index(current[i])
                swap = (i, j)
                break
        return swap

    def _calculate_makespan(self, solution: List[int]) -> Tuple[float, ScheduleInfo]:
        schedule = calculate_makespan_with_schedule(self.jobs, self.params, solution)
        return schedule.makespan, schedule

    def run(self) -> Tuple[List[int], float, ScheduleInfo]:
        start_time = time.time()
        current_solution = self._generate_initial_solution()
        current_makespan, current_schedule = self._calculate_makespan(current_solution)
        self.best_order = copy.deepcopy(current_solution)
        self.best_makespan = current_makespan
        self.best_schedule = current_schedule
        self.convergence_history.append(self.best_makespan)

        for _ in range(self.max_iter - 1):
            neighbors = self._generate_neighbors(current_solution)
            # 评估所有邻域解
            neighbor_scores = []
            for n in neighbors:
                makespan, schedule = self._calculate_makespan(n)
                swap = self._get_swap(current_solution, n)
                neighbor_scores.append((n, makespan, schedule, swap))
            # 按Makespan升序排序
            neighbor_scores.sort(key=lambda x: x[1])
            # 选择最优非禁忌解
            selected = None
            for n, makespan, schedule, swap in neighbor_scores:
                if not self._is_tabu(swap) or makespan < self.best_makespan:
                    selected = (n, makespan, schedule, swap)
                    break
            # 更新当前解和禁忌表
            current_solution, current_makespan, current_schedule, swap = selected
            self._update_tabu_list(swap)
            # 更新全局最优
            if current_makespan < self.best_makespan:
                self.best_makespan = current_makespan
                self.best_order = copy.deepcopy(current_solution)
                self.best_schedule = current_schedule
            # 记录收敛历史
            self.convergence_history.append(self.best_makespan)

        print(f"TS运行时间：{time.time() - start_time:.2f}s，最优Makespan：{self.best_makespan:.2f}")
        return self.best_order, self.best_makespan, self.best_schedule


# ========================= 可视化函数 =========================
def plot_gantt(schedule: ScheduleInfo, algorithm_name: str, instance_id: int, n_jobs: int):
    """绘制甘特图（配气+混匀+分析三阶段）"""
    plt.rcParams['font.sans-serif'] = ['SimHei']  # 支持中文
    plt.rcParams['axes.unicode_minus'] = False

    # 颜色配置
    colors = {
        "gas": ['#FF6B6B', '#4ECDC4', '#45B7D1', '#96CEB4'],  # 配气设备颜色
        "mix": ['#FECA57', '#FF9FF3', '#54A0FF', '#5F27CD'],  # 混匀设备颜色
        "test": ['#00D2D3', '#FF9F43', '#10AC84', '#EE5A24']  # 分析设备颜色
    }

    # 创建子图
    fig, (ax1, ax2, ax3) = plt.subplots(3, 1, figsize=(12, 8), sharex=True)
    fig.suptitle(f'算例{instance_id:02d}（{n_jobs}个作业）-{algorithm_name}甘特图', fontsize=14, fontweight='bold')

    # -------------------------- 1. 配气阶段甘特图 --------------------------
    ax1.set_title('配气阶段', fontsize=12)
    ax1.set_ylabel('设备编号', fontsize=10)
    gas_machines = set([v[2] for v in schedule.gas_schedule.values()])
    ax1.set_yticks(list(gas_machines))
    ax1.set_ylim(-0.5, len(gas_machines) - 0.5)

    for job_idx, (start, end, machine_id) in schedule.gas_schedule.items():
        color = colors["gas"][machine_id % len(colors["gas"])]
        rect = Rectangle((start, machine_id), end - start, 0.8,
                         facecolor=color, edgecolor='black', linewidth=0.5)
        ax1.add_patch(rect)
        ax1.text((start + end) / 2, machine_id + 0.4, f'J{job_idx}',
                 ha='center', va='center', fontsize=8)

    # -------------------------- 2. 混匀阶段甘特图 --------------------------
    ax2.set_title('混匀阶段', fontsize=12)
    ax2.set_ylabel('设备编号', fontsize=10)
    mix_machines = set([v[2] for v in schedule.mix_schedule.values()])
    ax2.set_yticks(list(mix_machines))
    ax2.set_ylim(-0.5, len(mix_machines) - 0.5)

    for job_idx, (start, end, machine_id) in schedule.mix_schedule.items():
        color = colors["mix"][machine_id % len(colors["mix"])]
        rect = Rectangle((start, machine_id), end - start, 0.8,
                         facecolor=color, edgecolor='black', linewidth=0.5)
        ax2.add_patch(rect)
        ax2.text((start + end) / 2, machine_id + 0.4, f'J{job_idx}',
                 ha='center', va='center', fontsize=8)

    # -------------------------- 3. 分析阶段甘特图 --------------------------
    ax3.set_title('分析阶段', fontsize=12)
    ax3.set_xlabel('时间', fontsize=10)
    ax3.set_ylabel('作业编号', fontsize=10)
    job_ids = list(schedule.test_schedule.keys())
    ax3.set_yticks(job_ids)
    ax3.set_ylim(-0.5, len(job_ids) - 0.5)

    for job_idx, (start, end, comp_machines) in schedule.test_schedule.items():
        # 用不同颜色表示不同组分的检测设备
        comp_colors = {c: colors["test"][mid % len(colors["test"])] for c, mid in comp_machines.items()}
        # 绘制作业的整体分析时间段（透明背景）
        rect = Rectangle((start, job_idx), end - start, 0.8,
                         facecolor='lightgray', alpha=0.3, edgecolor='black', linewidth=0.5)
        ax3.add_patch(rect)
        # 标注组分和设备
        comp_text = " | ".join([f"{c}(M{mid})" for c, mid in comp_machines.items()])
        ax3.text((start + end) / 2, job_idx + 0.4, comp_text,
                 ha='center', va='center', fontsize=7)

    # 统一x轴范围
    max_time = schedule.makespan * 1.1  # 留10%余量
    ax1.set_xlim(0, max_time)
    ax2.set_xlim(0, max_time)
    ax3.set_xlim(0, max_time)

    # 添加网格
    for ax in [ax1, ax2, ax3]:
        ax.grid(True, axis='x', alpha=0.3)
        ax.set_axisbelow(True)

    plt.tight_layout()
    # 保存图片
    if not os.path.exists(PLOT_FOLDER):
        os.makedirs(PLOT_FOLDER)
    save_path = os.path.join(PLOT_FOLDER, f"instance_{instance_id:02d}_{algorithm_name}_gantt.png")
    plt.savefig(save_path, dpi=300, bbox_inches='tight')
    plt.show()
    print(f"甘特图已保存至：{save_path}")


def plot_convergence(convergence_data: Dict[str, List[float]], instance_id: int, n_jobs: int):
    """绘制四种算法的收敛曲线对比图"""
    plt.rcParams['font.sans-serif'] = ['SimHei']
    plt.rcParams['axes.unicode_minus'] = False

    fig, ax = plt.subplots(1, 1, figsize=(10, 6))
    fig.suptitle(f'算例{instance_id:02d}（{n_jobs}个作业）- 算法收敛曲线对比', fontsize=14, fontweight='bold')

    # 曲线配置
    line_styles = {
        "GA": ('-', 'o'),
        "SA": ('--', 's'),
        "PSO": (':', '^'),
        "TS": ('-.', 'd')
    }
    colors = {
        "GA": '#FF6B6B',
        "SA": '#4ECDC4',
        "PSO": '#45B7D1',
        "TS": '#96CEB4'
    }

    # 绘制每条曲线（统一长度）
    min_len = min(len(history) for history in convergence_data.values())
    for algo_name, history in convergence_data.items():
        history_trimmed = history[:min_len]
        iter_range = range(min_len)
        style, marker = line_styles[algo_name]
        ax.plot(iter_range, history_trimmed, label=algo_name, color=colors[algo_name],
                linestyle=style, marker=marker, markersize=2, alpha=0.8, linewidth=1.5)

    # 设置标签和图例
    ax.set_xlabel('迭代次数', fontsize=12)
    ax.set_ylabel('最优Makespan', fontsize=12)
    ax.legend(loc='upper right', fontsize=10)
    ax.grid(True, alpha=0.3)
    ax.set_axisbelow(True)

    # 保存图片
    save_path = os.path.join(PLOT_FOLDER, f"instance_{instance_id:02d}_convergence.png")
    plt.savefig(save_path, dpi=300, bbox_inches='tight')
    plt.show()
    print(f"收敛曲线图已保存至：{save_path}")


# ========================= 主函数 =========================
def main():
    print("=" * 60)
    print("          标气生产车间调度优化系统（遗传/模拟退火/粒子群/禁忌搜索）")
    print("=" * 60)
    print("\n提示：请确保已安装必要依赖库，执行命令：")
    print("pip install numpy matplotlib")
    print("=" * 60)

    # 步骤1：检查并生成算例（如果已生成旧格式算例，先删除）
    old_instances = False
    if os.path.exists(INSTANCE_FOLDER):
        files = os.listdir(INSTANCE_FOLDER)
        if len(files) > 0:
            # 检查是否为旧格式（包含Job对象的序列化文件）
            test_file = os.path.join(INSTANCE_FOLDER, files[0])
            with open(test_file, "rb") as f:
                try:
                    data = pickle.load(f)
                    if "jobs" in data:  # 旧格式包含"jobs"键（直接序列化Job对象）
                        old_instances = True
                except:
                    old_instances = True

    if old_instances:
        print("\n检测到旧格式算例，正在删除并重新生成...")
        import shutil
        shutil.rmtree(INSTANCE_FOLDER)
        os.makedirs(INSTANCE_FOLDER)
        generate_all_instances()
    elif not os.path.exists(INSTANCE_FOLDER) or len(os.listdir(INSTANCE_FOLDER)) != INSTANCE_NUM:
        print(f"\n未检测到完整算例，开始生成{INSTANCE_NUM}个算例...")
        generate_all_instances()
        print("算例生成完成！")
    else:
        print(f"\n检测到已生成{INSTANCE_NUM}个算例，跳过生成步骤")

    # 步骤2：用户选择算例
    print("\n" + "-" * 30)
    print("算例列表（作业数递增）：")
    for i in range(INSTANCE_NUM):
        print(f"  算例{i + 1:02d}：{INSTANCE_JOBS[i]}个作业")
    print("-" * 30)

    while True:
        try:
            instance_id = int(input(f"\n请输入要运行的算例编号（1~{INSTANCE_NUM}）："))
            if 1 <= instance_id <= INSTANCE_NUM:
                break
            else:
                print(f"输入错误！请输入1~{INSTANCE_NUM}之间的整数")
        except ValueError:
            print("输入错误！请输入有效的整数")

    # 步骤3：加载算例
    print(f"\n正在加载算例{instance_id:02d}...")
    jobs, params, n_jobs = load_instance(instance_id)
    print(f"算例加载成功：{n_jobs}个作业，配气设备{params.m_gas}台，混匀设备{params.m_mix}台")

    # 步骤4：初始化并运行四种算法
    print("\n" + "=" * 50)
    print("开始运行四种调度算法...")
    print("=" * 50)

    # 初始化算法
    ga = GeneticAlgorithm(jobs, params, **ALGORITHM_PARAMS["GA"])
    sa = SimulatedAnnealing(jobs, params, **ALGORITHM_PARAMS["SA"])
    pso = ParticleSwarmOptimization(jobs, params, **ALGORITHM_PARAMS["PSO"])
    ts = TabuSearch(jobs, params, **ALGORITHM_PARAMS["TS"])

    # 运行算法
    ga_order, ga_makespan, ga_schedule = ga.run()
    sa_order, sa_makespan, sa_schedule = sa.run()
    pso_order, pso_makespan, pso_schedule = pso.run()
    ts_order, ts_makespan, ts_schedule = ts.run()

    # 步骤5：输出结果对比
    print("\n" + "=" * 50)
    print("算法结果对比：")
    print(f"遗传算法（GA）：最优Makespan = {ga_makespan:.2f}")
    print(f"模拟退火（SA）：最优Makespan = {sa_makespan:.2f}")
    print(f"粒子群算法（PSO）：最优Makespan = {pso_makespan:.2f}")
    print(f"禁忌搜索（TS）：最优Makespan = {ts_makespan:.2f}")
    print("=" * 50)

    # 步骤6：绘制甘特图（选择最优算法的甘特图）
    print("\n开始绘制甘特图...")
    # 选择Makespan最小的算法绘制甘特图
    best_algo = min(["GA", "SA", "PSO", "TS"], key=lambda x: eval(f"{x.lower()}_makespan"))
    best_schedule = eval(f"{best_algo.lower()}_schedule")
    plot_gantt(best_schedule, best_algo, instance_id, n_jobs)

    # 步骤7：绘制收敛曲线
    print("\n开始绘制收敛曲线...")
    convergence_data = {
        "GA": ga.convergence_history,
        "SA": sa.convergence_history,
        "PSO": pso.convergence_history,
        "TS": ts.convergence_history
    }
    plot_convergence(convergence_data, instance_id, n_jobs)

    print("\n" + "=" * 60)
    print("调度优化完成！所有图表已保存至 plots 文件夹")
    print("=" * 60)


if __name__ == "__main__":
    main()